package com.sicheng.lc.周赛.分类.堆.双堆;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/8 23:41
 */
public class 会议室III {
    //https://leetcode.cn/problems/meeting-rooms-iii/

    public int mostBooked(int n, int[][] meetings) {
        //(结束时间，会议室编号)
        PriorityQueue<int[]> using = new PriorityQueue<>(n,
                (a, b) -> {
                    if (a[0] == b[0])
                        return a[1] - b[1];
                    return a[0] - b[0];
                }
        );
        //空闲会议室的编号
        PriorityQueue<Integer> free = new PriorityQueue<>(n);
        for (int i = 0; i < n; i++) {
            free.add(i);
        }

        int[] cnt = new int[n];
        Arrays.sort(meetings, Comparator.comparingInt(e -> e[0]));
        for (int[] meeting : meetings) {
            int st = meeting[0], end = meeting[1];
            while (!using.isEmpty() && using.peek()[0] <= st)
                free.offer(using.poll()[1]);
            int i;
            if (free.isEmpty()) {
                assert using.peek() != null;
                end += using.peek()[0] - st;
                i = using.peek()[1];
                using.poll();
            } else {
                i = free.poll();
            }
            cnt[i]++;
            using.offer(new int[]{end, i});
        }

        int x = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > cnt[x])
                x = i;
        }
        return x;
    }
}
